/**
 * @ClassName KP27_MergeKSortedLists
 * @Description: TODO
 * @Author: JCC
 * @CreateTime: 2023/10/25 17:57
 */

import java.util.PriorityQueue;

/**
 * 合并K个升序链表
 */
public class KP27_MergeKSortedLists {
    // 测试链接：https://leetcode.cn/problems/merge-k-sorted-lists/

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }
    }

    /**
     * 使用小根堆数据结构实现链表的合并
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null) {
            return null;
        }
        if (lists.length == 1) {
            return lists[0];
        }
        PriorityQueue<ListNode> smallHeap = new PriorityQueue<>((o1, o2) -> {
            return o1.val - o2.val;
        });
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                smallHeap.add(lists[i]);
            }
        }
        ListNode head = new ListNode(-1);
        ListNode pre = head;
        while (!smallHeap.isEmpty()) {
            ListNode cur = smallHeap.poll();
            pre.next = cur;
            pre = cur;
            if (cur.next != null) {
                smallHeap.add(cur.next);
            }
        }
        return head.next;
    }

}
